package leetcode.weekly.week297;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import leetcode.IDebug;
import leetcode.helper.H;

//Solution4Test
public class Solution6 implements IDebug {

	// Solution4Test
	public long distinctNames(String[] ideas) {
		Map<String, int[]> keyTail = new HashMap<>();
		Arrays.sort(ideas, (a, b) -> {
			if (a.substring(1).equals(b.substring(1))) {
				return a.charAt(0) - b.charAt(0);
			} else {
				return a.substring(1).compareTo(b.substring(1));
			}
		});
//		H.printObject(ideas);
		Map<Character, List<String>> keyHead = new HashMap<>();
		Set<String> set = new HashSet<>();
		int[] headCnt = new int[26];
		for (int i = 0; i < ideas.length; i++) {
			String string = ideas[i];
			set.add(string);
			char head = string.charAt(0);
			String tail = string.substring(1);
			int[] heads = keyTail.getOrDefault(tail, new int[] { 0, 0 });
			int headIndex = 1 << (head - 'a');
			if ((heads[0] & headIndex) == 0) {
				heads[0] |= headIndex;
				heads[1] += 1;
				keyTail.put(tail, heads);
			}
			List<String> tails = keyHead.getOrDefault(head, new ArrayList<>());
			tails.add(tail);
			keyHead.put(head, tails);
			headCnt[head - 'a']++;
		}
		int total = ideas.length;
		long ans = 0;
		for (int i = 0; i < ideas.length; i++) {
			String string = ideas[i];
			char head = string.charAt(0);
			String tail = string.substring(1);
			int sub1 = keyHead.get(head).size();
			int sub2 = keyTail.get(tail)[1];
			int cur = (total - sub1 - sub2 + 1);
			ans += (long) (total - sub1 - sub2 + 1);
		}
		return ans;
	}

	@Override
	public void debug4() {
		// ["ra","df","dk","rk"]
		// ["pzydbfwiw","ringlxh","dcn","drmvufbt","qzydbfwiw","rrmvufbt"]
//		["pzydbfwiw","ow","ssipb","jucpsquexm","ffuzder","uftruik","ringlxh","csdbtsvg","openygbaix","dcn","sz","ejfpsea","vjfpsea","drmvufbt","qzydbfwiw","lqxik","rrmvufbt"]
		// ["pzydbfwiw","lvvyshmd","ow","ssipb","jucpsquexm","ffuzder","uftruik","ringlxh","sjlxouiv","csdbtsvg","openygbaix","dcn","sze","ttptd","atxp","ejfpsea","vjfpsea","drmvufbt","qzydbfwiw","lqxik","bjo","rrmvufbt"]
		H.compare(2, this.distinctNames(H.str2array2("[\"ra\",\"df\",\"dk\",\"rk\"]")));
//		H.compare(2, this.distinctNames(H.str2array2("[\"ringlxh\",\"dcn\",\"drmvufbt\",\"rrmvufbt\"]")));
//		H.compare(18, this.distinctNames(H.str2array2("[\"pzydbfwiw\",\"ringlxh\",\"dcn\",\"drmvufbt\",\"qzydbfwiw\",\"rrmvufbt\"]")));
//		H.compare(438, this.distinctNames(H.str2array2("[\"pzydbfwiw\",\"lvvyshmd\",\"ow\",\"ssipb\",\"jucpsquexm\",\"ffuzder\",\"uftruik\",\"ringlxh\",\"sjlxouiv\",\"csdbtsvg\",\"openygbaix\",\"dcn\",\"sze\",\"ttptd\",\"atxp\",\"ejfpsea\",\"vjfpsea\",\"drmvufbt\",\"qzydbfwiw\",\"lqxik\",\"bjo\",\"rrmvufbt\"]")));
//		["pzydbfwiw","lvvyshmd","ow","ssipb","jucpsquexm","ffuzder","uftruik","ringlxh","jz","sjlxouiv","csdbtsvg","openygbaix","dcn","rr","hwql","ok","yy","sze","ttptd","atxp","ejfpsea","vjfpsea","lj","drmvufbt","qzydbfwiw","lqxik","bjo","rrmvufbt"]
//		H.compare(716, this.distinctNames(H.str2array2(
//				"[\"pzydbfwiw\",\"lvvyshmd\",\"ow\",\"ssipb\",\"jucpsquexm\",\"ffuzder\",\"uftruik\",\"ringlxh\",\"jz\",\"sjlxouiv\",\"csdbtsvg\",\"openygbaix\",\"dcn\",\"rr\",\"hwql\",\"ok\",\"yy\",\"sze\",\"ttptd\",\"atxp\",\"ejfpsea\",\"vjfpsea\",\"lj\",\"drmvufbt\",\"qzydbfwiw\",\"lqxik\",\"bjo\",\"rrmvufbt\"]")));
//		H.compare(4934, this.distinctNames(H.str2array2(
//				"[\"sfuzder\",\"spklurny\",\"kvdolme\",\"kbbdklkpgk\",\"za\",\"mdbsmnjiu\",\"pzydbfwiw\",\"lvvyshmd\",\"ow\",\"ssipb\",\"jucpsquexm\",\"ffuzder\",\"uftruik\",\"ringlxh\",\"jz\",\"sjlxouiv\",\"csdbtsvg\",\"openygbaix\",\"dcn\",\"r\",\"hwql\",\"ok\",\"y\",\"sze\",\"ttptd\",\"atxp\",\"ejfpsea\",\"vjfpsea\",\"lj\",\"drmvufbt\",\"zxambug\",\"ozpxq\",\"qzydbfwiw\",\"lqxik\",\"bjo\",\"rrmvufbt\",\"jvl\",\"rzxaaa\",\"nmfydhawa\",\"shlwkf\",\"rcl\",\"hhn\",\"yrmcsc\",\"yieuzizaeh\",\"nrmvufbt\",\"rinsldgdpp\",\"wqg\",\"tyhkgqcu\",\"rsdbtsvg\",\"zvehtqiqxa\",\"jtz\",\"mjaguebiy\",\"fztbpozhf\",\"zzpxq\",\"ue\",\"foktqxiqe\",\"ztf\",\"dn\",\"lxambug\",\"kinsldgdpp\",\"jhn\",\"k\",\"i\",\"qxtava\",\"roktqxiqe\",\"hr\",\"bwzw\",\"mot\",\"cadj\",\"x\",\"bcep\",\"u\",\"kzydbfwiw\",\"ahku\",\"ijo\"]")));
//		H.compare(2, this.distinctNames(H.str2array2("[\"aaa\",\"baa\",\"caa\",\"bbb\",\"cbb\",\"dbb\"]")));
//		H.compare(6, this.distinctNames(H.str2array2("[\"coffee\",\"donuts\",\"time\",\"toffee\"]")));
//		H.compare(0, this.distinctNames(H.str2array2("[\"lack\",\"back\"]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution6 so = new Solution6();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
	}

}
